\section{指标与 $n$ 次剩余}

\begin{frame}{指标}


我们已知道， 对 $m=p^{s}$ 或 $2 p^{s}$, 模 $m$ 的原根存在 ($p$ 为奇素数). 设 $g$ 为模 $m$ 的原根， 则 $U_{m}=(\mathbb{Z} / m \mathbb{Z})^{*}=\langle\bar{g}\rangle=\left\{1, \bar{g}, \cdots, \bar{g}^{\varphi(m)-1}\right\}$ (为循环群). 本节讨论此情形。

\pause
\begin{definition}%定义1
  [指标]
  设 $g$ 为模 $m$ 的原根， 整数 $a$ 与 $m$ 互素， 若整数 $i$ ($0 \leqslant i \leqslant$ $\varphi(m)-1)$ 使
\[
\bar{a}=\bar{g}^{i}, \quad \text { 即~} a \equiv g^{i}\left(\mod m\right),
\]
则称 $i$ 为 $a$ (模 $m$) 的\emph{指标} (index), 或\emph{指数}， 或 \emph{(离散)对数}(logarithm)（对于基 $g$), 常记
\[
i=\operatorname{ind}_{g} a \quad\text {(或 $\operatorname{ind} a$, 在不致混淆时). }
\]
\end{definition}

\pause
注意 $\bar{g}$ 的阶为 $\varphi(m)$, 故 $\bar{a}=\bar{g}^{i}=\bar{g}^{i+k \varphi(m)}$ (对整数 $k$); 
\pause
而若 $\bar{g}^{i}=\bar{g}^{j}$, 则
\[
\bar{g}^{i-j}=1, \quad \varphi(m) \mid i-j, \quad i=j+k \varphi(m) \quad \text { (对某整数$k$). }
\]
故
\[
  \bar{a}=\bar{g}^{j} \Leftrightarrow j \equiv \operatorname{ind}_{g} a \quad\left(\mod \varphi(m)\right).
\]
\pause
因此，指标 $\operatorname{ind}_{g} a$ 实为模 $\varphi(m)$ 的一个同余类，或者说是在模 $\varphi(m)$ 意义下定义的。
\end{frame}

\begin{frame}

\begin{lemma}%引理1
\color{gray}
  (1) (指标与一般对数性质相仿) 设 $a, b$ 与 $m$ 互素，则
  \[
  \begin{aligned}
  \operatorname{ind}_{g}(a b) & \equiv \operatorname{ind}_{g} a+\operatorname{ind}_{g} b \quad\left(\mod \varphi(m)\right)\\
\operatorname{ind}_{g}\left(a^{r}\right) & \equiv r \operatorname{ind}_{g} a \quad\left(\mod \varphi(m)\right).
\end{aligned}
\]

(2) (指标可换底 (原根), 犹如对数换底) 设 $g, g_{1}$ 皆为模 $m$ 的原根，则
\[
  \operatorname{ind}_{g} a\equiv \operatorname{ind}_{g} g_{1} \cdot \operatorname{ind}_{g_{1}} a \quad\left(\mod \varphi(m)\right).
\]

(3) 设模 $m$ 有原根 $g$, 则 $\operatorname{ord}_{m}(a)=\frac{\varphi(m)}{(\text { ind } a, \varphi(m))}$.
%(2) 在 $U_{m}=(\mathbb{Z} / m \mathbb{Z})^{*}$ 中， 阶 (周期) 为 $d$ (其中 $d \mid \varphi(m)$ ) 的元素个数是 $\varphi(d)$.

%(3) 模 $m$ 的所有原根恰为 $\left\{g^{i} \mid(i, \varphi(m))=1\right\}$, 个数为 $\varphi(\varphi(m))$.
\end{lemma}

\pause
\color{gray}
由(1)知：对固定的原根 $g$ 取指标引起群同构 (将乘法群同构映射到指标的加法群)
\[
  (\mathbb{Z} / m \mathbb{Z})^{*} \xrightarrow{\cong} \mathbb{Z} / \varphi(m) \mathbb{Z}, \quad a \mapsto \operatorname{ind}_{g} a.
\]

\pause
\vspace{-.5em}
\begin{proof}
\color{gray}
  (1) 显然。

(2) 设 $g_{1} \equiv g^{b} \left(\mod m\right)$, $\operatorname{ind}_{g_1} a=s$,
则
$a=g_{1}^{s}=g^{b s} \left(\mod m\right),$ 从而
\[
  \operatorname{ind}_{g} a \equiv b s=\operatorname{ind}_{g} g_{1} \cdot \operatorname{ind}_{g_{1}} a \quad\left(\mod \varphi(m)\right).
\]

(3) 应用 \S3.1 引理 5 到 $\bar{g}^{i} \in(\mathbb{Z} / m \mathbb{Z})^{*}=\langle\bar{g}\rangle$, 即可得 ($\bar{g}$ 的阶为 $\varphi(m)$).
\end{proof}
\end{frame}

%\begin{frame}
%  \begin{proof}
%   (1) 应用 \S3.1 引理 5 到 $\bar{g}^{i} \in(\mathbb{Z} / m \mathbb{Z})^{*}=\langle\bar{g}\rangle$, 即可得 $(\bar{g}$ 的阶为 $\varphi(m)$.
%
%    (2) 由 (1) 知 $\operatorname{ord}(\bar{a})=d$ 相当于
%  \[
%  \varphi(m) /(i, \varphi(m))=d, \varphi(m) / d=(i, \varphi(m))=d^{\prime}
%\]
%记
%\[
%i=j d^{\prime}, \quad \varphi(m)=d d^{\prime},
%\]
%则上式为 $\left(j d^{\prime}, d d^{\prime}\right)=d^{\prime}$, 即 $(j, d)=1$. 这种 $j$ (在 1 与 $d$ 间) 的个数为 $\varphi(d)$.
%
%(3) $g^{i}$ 为原根相当于 $\bar{g}^{i}$ 的阶为 $\varphi(m)$, 这当且仅当 $(i, \varphi(m))=1$.
%\end{proof}
%
%指标可换底 (原根), 犹如对数换底。 设 $g, g_{1}$ 皆为模 $m$ 的原根，
%\[
%g_{1} \equiv g^{b} \quad\left(\mod m\right)
%\]
%则
%\[
%  \begin{gathered}
%  a=g_{1}{ }^{s}=g^{b s} \quad\left(\mod m\right) \\
%\operatorname{ind}_{g} a=b s=\operatorname{ind}_{g} g_{1} \cdot \operatorname{ind}_{g_{1}} a \quad\left(\mod \varphi(m)\right)
%\end{gathered}
%\]
%\end{frame}

\begin{frame}{$n$ 次剩余}
原根存在的时候， 指标使对许多问题的理解和计算都简洁化了。 以下考虑指标到 $n$ 次剩余问题的应用。

\begin{definition}%定义2
[$n$ 次剩余] 设 $(a, m)=1$, 若同余式
\begin{equation*}
x^{n} \equiv a \quad\left(\mod m\right) \tag{1}
\end{equation*}
有整数解 $x$, 则称 $a$ 为\emph{模 $m$ 的 $n$ 次剩余} ( $n$-th power residue modulo $m$ ), 否则称为 \emph{$n$ 次非剩余} ( $n$-th power nonresidue).
\end{definition}

简言之， $n$ 次剩余就是 $n$ 次幂 $\left(\mod m\right)$.

\pause
如果模$m$有原根 $g$ (例如 $m=p^{s}$ 为奇数幂), $n$ 次剩余问题特别简单 (设 $a=g^{i}$):

\pause
  (i) 当 $n \mid i$ 时，令$i=kn$,  $g^{i}=g^{k n}$ 是 $n$ 次剩余 (即 $n$ 次幂 $\left(\mod m\right)$).

  \pause
 (ii) 当 $n$ 与 $\varphi(m)$ 互素时， $1=u n+v \varphi(m)$ (Bézout 等式), 故
 \[
 g^{1}=g^{u n} \cdot g^{u \varphi(m)}=g^{u n}
 \]
 即知 $g$ 是 $n$ 次剩余，从而任意 $a=g^{i}$ 都是。

 \pause
 (iii) 对一般的 $n$, 上述显示：

$n$ 在 $\varphi(m)$ 外的因子， $n /(n, \varphi(m))$, 不阻碍任意 $a$ 成为 $n$ 次剩余;

而 $n$ 在 $\varphi(m)$ 内的因子， $(n, \varphi(m))$, 要整除 $i=\operatorname{ind} a$ 才能使 $a$ 为 $n$ 次剩余。
\end{frame}

\begin{frame}
  \begin{theorem}%定理1
  设模 $m$ 有原根 $g,(a, m)=1$. 考虑 $x^{n} \equiv a\left(\mod m\right)$. 那么

  (1) 我们有
  \[
  \begin{aligned}
  \text { $a$  是模 $m$  的 $n$ 次剩余 } \quad &
     \Leftrightarrow  \quad (n, \varphi(m)) \mid \operatorname{ ind } a \\
     & \Leftrightarrow  \quad a^{\frac{\varphi(m)}{(n, \varphi(m))}} \equiv 1 \left(\mod m\right),
\end{aligned}
\]
且此时 $x^{n} \equiv a\left(\mod m\right)$ 的解 $x$ 的个数为 $d=(n, \varphi(m))$.

(2) $n$ 次剩余 $a$ 的个数为 $\varphi(m) / d$ (在 $(\mathbb{Z} / m \mathbb{Z})$ 的一个代表元系中). 

~

\pause
特别可知， $m>2$ 时，
\[
  \begin{aligned}
x^{2} \equiv a \left(\mod m\right) \text {~有解~}(\text {即$a$为二次剩余 })\quad &
\Leftrightarrow \quad 2 \mid \operatorname { ind } a \\
 & \Leftrightarrow\quad  a^{\varphi(m) / 2} \equiv 1 \left(\mod m\right),
\end{aligned}
\]
且此时 $x^{2} \equiv a\left(\mod m\right)$ 的解数为 $2$. 
二次剩余 $a$ 的个数为 $\varphi(m) / 2$.
\end{theorem}

\pause
\begin{proof}
   (1) 设 $a=g^{i}, x=g^{y}$, 则
 $x^{n} \equiv a \left(\mod m\right)$  等价于 $n y \equiv i \left(\mod \varphi(m)\right).$
 \pause
 右式有解当且仅当 $d \mid i$, 即$d\mid \operatorname{ind} a$, 
 且 (模$\varphi(m)$不同的) 解$y$的个数为 $d$ (见 \S2.3 系 2),
 从而右式有解时左式有解且解$x$的个数为$d$.
 \pause
 另一方面，
 $a^{\varphi(m) / d} \equiv g^{i \varphi(m) / d} \equiv 1 \left(\mod m\right)$ 当且仅当
 $\varphi(m) \mid(i \varphi(m) / d)$ (因  $g$ 的阶为 $\varphi(m)$), 当且仅当
 $i / d$为整数 (即$(n,\varphi(m))\mid \operatorname{ind} a$). 

 \pause
 (2) $n$ 次剩余的个数即是指标集 $\{0,1,2, \cdots, \varphi(m)-1\}$ 中 $d$ 的倍数的个数， 是为 $\varphi(m) / d$.
 \end{proof}

\end{frame}

\begin{frame}
\begin{example}
模 $m=11$ 的最小原根为 $2$, $(\mathbb{Z} / m \mathbb{Z})^*$ 元素列表为

\begin{center}
  \begin{tabular}{c|c|c|c|c|c|c|c|c|c}
    \hline
  $\overline{1}$ & $\overline{2}$ & $\overline{2}^{2}$ & $\overline{2}^{3}$ & $\overline{2}^{4}$ & $\overline{2}^{5}$ & $\overline{2}^{6}$ & $\overline{2}^{7}$ & $\overline{2}^{8}$ & $\overline{2}^{9}$ \\
\hline
$\overline{1}$ & $\overline{2}$ & $\overline{4}$ & $\overline{8}$ & $\overline{5}$ & $\overline{10}$ & $\overline{9}$ & $\overline{7}$ & $\overline{3}$ & $\overline{6}$ \\
\hline
\end{tabular}
\end{center}

\pause
因 $a$ 为 $n$ 次剩余条件为 $(n, 10) \mid \operatorname{ind} a$. 在 $n=2,3,4,5$ 时依次为
\[
2 \mid \operatorname{ind} a, 1 \mid \operatorname{ind} a, 2 \mid \operatorname{ind} a, 5 \mid \operatorname{ind} a.
\]
\pause
故 $2$ (和 $4$) 次剩余者为： $1,4,5,9,3$ (在一个代表元系中， 恰 $\varphi(m) / d=10 / 2$个). 
\pause
而所有元素全为 $3$ 次剩余。
$5$ 次剩余为 $1,10$ (恰 $10 / 5=2$ 个). 
\pause
例如，我们可直接计算验证
\[
  5^{2} \equiv 9^{3} \equiv 4^{4} \equiv 3 \quad\left(\mod 11\right), \quad 2^{5} \equiv 10 \quad\left(\mod 11\right).
\]
\end{example}

\begin{example}
  解$x^4\equiv 13\left( \mod 17 \right)$. 
  有$m=17$, $\varphi(m)=16$, $n=4$, $a=13$, $d=(4,\varphi(17))=4$.
  容易检验出$3$为最小的模$17$原根。
  可依次算出$3^k\left( \mod 17 \right)$确定出$\ind 13=4$.%
  \footnote{我们也可如下加些判断来确定。注意到
  $13^2\equiv (-4)^2\equiv -1\left( \mod 17 \right)$,
  我们知$\ord_{17}(13)=4$. $16$阶循环群$U_{17}$的$4$阶子群只有$\pair{3^4}$,
  此$4$阶循环群的生成元只有$3^4, 3^{-4}$. 故$13\in \{3^4, 3^{-4}\}\left( \mod 17 \right)$.
容易发现$3^4\equiv 13\left( \mod 17 \right)$. 因此$\ind 13=4$.  }
  既然$d\mid \ind 13$, 由定理1知
  $x^4\equiv 13\left( \mod 17 \right)$有解且有$4$个解。
  要确定这些解，令$x=3^y$. 由定理1的证明知$x$为解相当于其指标$y$满足
  $4y\equiv 4\left( \mod 16 \right)$.
  此方程有$4$个解$y\equiv 1, 5, 9, 13\left( \mod 16 \right)$. 故$4$个解$x=3^y$为
  $3, 3^5\equiv  5, 3^9\equiv 14,  3^{13}\equiv 12\left( \mod 17 \right).$
\end{example}
\end{frame}




\begin{frame}


  定理1中$a$为模$m$的$n$次剩余的等价条件$a^{\frac{\varphi(m)}{(n, \varphi(m))}} \equiv 1 \left(\mod m\right)$
的好处是不用取原根，不过一般而言只能用于判断，通常我们无法由此找到解 (某些情形下可以，见\S4.4)；另一个等价条件
  $(n, \varphi(m)) \mid \operatorname{ ind }_g a$
  乍看依赖于原根的选取，
  不过实际上并非如此，可取任意的原根$g$来判断；原根与指标的好处是可用于找到解。

~

\pause
 利用模 $m$ 的原根和指标考虑 $n$ 次剩余等问题的时候， 可按如下步骤。

 I. 求出原根 $g$. 当然是希望求出最小原根， 但并没有一定的公式， 需用试验的办法。 一般应先求出模素数 $p$ 的原根，再用 $\S 3.2$ 系 1 的方法求出模 $m$的原根 $g$ (参见上两节的证明).

 II. 列出 $(\mathbb{Z} / m \mathbb{Z})^{*}$ 的元素及其指标。 这只需原根 $g$ 不断自乘即可得到
 \[
 (\mathbb{Z} / m \mathbb{Z})^{*}=\langle\bar{g}\rangle=\left\{1, \bar{g}, \cdots, \bar{g}^{\varphi(m)-1}\right\}
 \]

 III. 按照定理 1 , 由指标定出模 $m$ 的 $n$ 次剩余。

 ~

 \pause
 还可求出 $(\mathbb{Z} / m \mathbb{Z})^{*}$ 中元素的 $n$ 次方集 $(\mathbb{Z} / m \mathbb{Z})^{* n}$, 
 即得模 $m$ 的 $n$ 次剩余集。 
 \pause
 例如模 $m=11$ 时， $(\mathbb{Z} / m \mathbb{Z})^{*}=\{\overline{1}, \overline{2}, \overline{3}, \overline{4}, \overline{5}, \overline{6}, \overline{7}, \overline{8}, \overline{9}, \overline{10}\}$. 
 \pause
 平方之得 $(\mathbb{Z} / m \mathbb{Z})^{* 2}=\{\overline{1}, \overline{4}, \overline{9}, \overline{5}, \overline{3}\}$. 故 $1,4,9,5,3$ 是模 $11$ 的二次剩余集。
 \pause
 取$5$次方得$(\mathbb{Z} / m \mathbb{Z})^{* 5}=\{\bar{1}, \overline{10}\}$, 
 因此$1, 10$是所有模$11$的$5$次剩余。
 \end{frame}

 \begin{frame}
   \begin{remark}%注记1
   原根与指标 (离散对数)在密码、信息安全 (公钥加密， public-key cryptography) 中有重要实际应用。 其原理是：已知 $m, g$ 和 $k$, 求方幂 $g^{k}\left(\mod m\right)$容易; 但反过来， 已知 $m, g$ 和 $a$, 求离散对数 $k\left(\right.$ 即满足 $\left.g^{k} \equiv a\left(\mod m\right)\right)$ 没有已知的有效算法。 最容易想到的 (naive)算法是逐个试验 $g^{2}, g^{3}, \cdots$ 直到 $g^{k} \equiv a\left(\mod m\right)$, 运行时间与 $\varphi(m)$ 为线性关系，与 $\varphi(m)$ 的位数为指标关系。 其他的算法也均非多项式时间 (对 $\varphi(m)$ 位数).

 实用中， 假定 $\mathrm{A}, \mathrm{B}, \mathrm{C}$ 等多人组中要相互通信， 可先选定 $m$ 和 $g($ 例如 $m=p=2 q+1$ 为大素数), 均可公开。 组中每人 (随机地) 私定密藏一数， 如 $k_{A}$, $k_{B}$ 等 (私钥); 各人计算出 $g^{k_{A}}, g^{k_{B}}$ 等并公开发布 (公钥). 若 $\mathrm{A}$ 欲向 $\mathrm{B}$ 发信息，则以 $\left(g^{k_{B}}\right)^{k_{A}}$ 为密码加密信息后发给 B. 而 B 接信息后， 会计算 $\left(g^{k_{A}}\right)^{k_{B}}$ 而得密码， 即可解密信息读取。 外人虽知公开的 $g$ 和 $g^{k_{A}}, g^{k_{B}}$, 但由此计算私钥 (离散对数) $k_{A}, k_{B}$ 是不可能的(目前如此).

 上述离散对数密码算法， 基础是循环群 $(\mathbb{Z} / m \mathbb{Z})^{*}=\langle\bar{g}\rangle$. 当然可以发展到其他循环群去。 最重要的发展有： (1) 有限域的（非零元）乘法群群 $\FF_q^{*}$ 特别是 $\mathbb{F}_{2^{n}}^{*}$. (2) 有限域上椭圆曲线的有理点群： $E\left(\mathbb{F}_{q}\right)$. 后者是目前最好的算法，也称为椭圆曲线算法 (ECC算法), 加密编码的时候， 是求椭圆曲线上两个有理点的和（这种求和通过一个很复杂的有理式进行，见 §5.1), 破密过程相当于反解这种求和， 很难。

\end{remark}

 \end{frame}

 \begin{frame}
\begin{remark}%注记2
原根和指标是初等数论的经典内容， 各种人门书都提及。 但仍有
一些问题至今不能解决。 例如：$2$ 是无限多素数的原根吗? 目前尚不知任何一个整数是无限多素数的原根。 Gupta-Murty 和 Brown (1984-1986) 得到： 除去最多两个例外， 每个素数是无限多素数的原根 (但哪个是例外不得而知， 目前个个有嫌疑). Artin 猜想： 若整数 $a$ 不是完全平方数， 不是 $-1$, 则 $a$ 是无限多素数的原根。 至今成谜。
\end{remark}

\begin{comment*}%评述
原根的存在， 尤其是模为奇素数幂时原根的存在， 极大地简化了同余类环单位群 $U_{m}$ 的结构， 其元素皆为原根之幂， 各有指标， 使问题清晰明了。这在理论和实用中意义重大， 后来发展为循环群理论。 论数者赞这 “原根之妙”曰：
\begin{poem}
原根之幂可周天，巡遍魔环可逆员。\\
从此喜模奇素幕， 逆员个个顶标签。
\end{poem}
\end{comment*}
\end{frame}

\begin{frame}{小结}

  \begin{enumerate}
    \item 设模$m$原根存在。$\bar{a}\in U_m$的指标指什么？如何用其指标表示出$\bar{a}$的阶？
    \item 何为模$m$的$n$次剩余？
    \item 说说模$m$有原根时与$m$互素的数是模$m$的$n$次剩余的等价条件。
    \item 模$m$有原根且与$m$互素的$a$为模$m$的$n$次剩余时$x^n\equiv a\left( \mod m \right)$的解有多少？
    \item 举例说说模$m$有原根时如何解$x^n\equiv a\left( \mod m \right)$.
  \end{enumerate}
  
\end{frame}
